package com.mlamp.动态规划;

import java.util.Arrays;

public class 不同的子序列II {

    public static void main(String[] args) {

    }

    public static int distinctSubseqII(String S) {
        int length = S.length();
        int MOD = 1_000_000_007;
        int dp[] = new int[length + 1];
        dp[0] = 1;
        int[] last = new int[26];
        Arrays.fill(last, -1);
        for (int i = 0; i < length; i++) {
            int x = S.charAt(i) - 'a';
            dp[i + 1] = dp[i] * 2 % MOD;
            if (last[x] >= 0) {
                dp[i + 1] -= dp[last[x]];
            }
            dp[i + 1] %= MOD;
            last[x] = i;
        }
        dp[length]--;
        if (dp[length] < 0) dp[length] += MOD;
        return dp[length];
    }
}
